/*
* 计数排序：
* 原始数组中取最大值，用这个最大值作为数组长度生成一个新的计数数组，如果最大值是10，就生成一个长度为10的空数组，遍历原始数组，原始数组中的每一个值，
* 都作为计数数组中的下标，如果原始数组中的值有重复，计数数组中下标对应的值的计数就相应的+重复的个数，
* 这样全部遍历完之后，就统计计数数组中每一个下标（在标记下标的时候就已经完成了排序，就只差计数有多少重复值）对应的值有多少个
*
* 空间换时间 值的差值不要太大 值得是自然数，不能有小数
* 分布式排序使用已经组织好的辅助结构（称为桶），然后进行合并，得到排好序的数组。
* 计数排序使用一个用来存储每个元素在原始数组中出现次数的临时数组。在所有元素都计数完成后，临时数组已经排序好并可以迭代以构建排序后的结果数组。
* 它是用来排序整数的优秀算法，时间复杂度为O（n+k），其中k是临时计数数组的大小
*
* */

//随机生成数组的函数
function creatArray(length){
    let array = new Array(length)
    for(let i = 0, len = length; i < len; i++){
        array[i] = Math.floor(Math.random()*length)
    }
    return array
}
let myArray = creatArray(10000)

function countingSort(arr){ //数组内容如果小于两个元素，没必要浪费时间
    if(arr.length < 2){
        return arr //直接返回数组
    }

    const maxValue = findMaxValue(arr) //取这个数组的最大值
    const countArr = new Array(maxValue) //创建计数数组
    arr.forEach(ele => { //ele是下标，原始数组的值是计数数组的下标
        if(!countArr[ele]){ //如果里面原本没有值，就计数为0，即从0开始
            countArr[ele] = 0
        }
        countArr[ele]++ //否则就是原先有值，计数器就++
    })
    let sortIndex = 0 //原始数组的计数器，从原始数组中开始排
    countArr.forEach((count, index) => {
        while(count > 0){ //只要计数数组中还有内容，就继续排序原始数组中的值
            console.log(index)
            arr[sortIndex++] = index //将原始数组中的值按照计数数组中的下标来排序
            count--
        }
    })
    return arr
}

function findMaxValue(arr){
    let max = arr[0]
    for(let i = 1; i < arr.length; i++){
        if(arr[i] > max){
            max = arr[i]
        }
    }
    return max
}

let arr = [0,1,3,4,2,1,0,0,2,1]
console.log(arr)
countingSort(arr)
console.log(arr)